package com.rr.middle;

/**
 * @author zhuangcanrun
 * @Date 2021/10/25/18:37
 * @description
 **/
/*
* https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
* */
public class SearchMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int column = matrix[0].length;
        if (row >= column) {
            for (int columnNum = 0; columnNum < column; columnNum++) {
                if (canFindFromColumn(matrix, columnNum, row, target)) {
                    return true;
                }
            }
        } else {
            for (int rowNum = 0; rowNum < row; rowNum++) {
                if (canFindFromRow(matrix[rowNum], column, target)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean canFindFromRow(int[] array, int column, int target) {
        int left = 0;
        int right = column - 1;
        if (array[left] > target || array[right] < target) {
            return false;
        }
        while (left < right) {
            int middle = (left + right) / 2;
            int tempTarget = array[middle];
            if (tempTarget == target) {
                return true;
            } else if (tempTarget > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return array[left] == target;
    }

    private boolean canFindFromColumn(int[][] matrix, int columnNum, int row, int target) {
        int top = 0;
        int bottom = row - 1;
        if (matrix[top][columnNum] > target || matrix[bottom][columnNum] < target) {
            return false;
        }
        while (top < bottom) {
            int middle = (top + bottom) / 2;
            int tempTarget = matrix[middle][columnNum];
            if (tempTarget == target) {
                return true;
            } else if (tempTarget > target) {
                bottom = middle - 1;
            } else {
                top = middle + 1;
            }
        }
        return matrix[top][columnNum] == target;
    }

    public static void main(String[] args) {
        SearchMatrix searchMatrix = new SearchMatrix();
//        int[][] a = new int[][]{{1,4,7,11,15}, {2,5,8,12,19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
        int[][] a = new int[][]{{1, 1}};
        System.out.println(searchMatrix.searchMatrix(a, 0));
    }
}
